package Leetcode;

import java.util.ArrayList;
import java.util.List;

public class problem22 {
    public static List<String> generateParenthesis(int n) {
        List<String> results = new ArrayList<>();
        parentTheses("",results,n,n);
        return results;
    }

    public static void parentTheses(String s, List<String> results,int left,int right){
        if(left == 0 && right == 0){
            results.add(s);
        }
        if(right > left){
            parentTheses(s+")",results,left,right - 1);
        }
        if(left > 0){
            parentTheses(s+"(",results,left - 1,right);
        }
    }

    public static void main(String[] args) {
        generateParenthesis(3);
    }

}
